package com.acwing.partition5;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AC487金明的预算方案 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int money = Integer.parseInt(s[0]), n = Integer.parseInt(s[1]);

        //key为主产品的id，value为主产品实体，如果该主产品有对应的附产品，则会添加到其中的slaveList中
        Map<Integer, MasterGoods> masterMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            s = reader.readLine().split("\\s+");
            int v = Integer.parseInt(s[0]), w = Integer.parseInt(s[1]), q = Integer.parseInt(s[2]);
            if (q == 0) {
                //该产品是个主产品
                masterMap.put(i, new MasterGoods(v, v * w));
            } else {
                //产品是从属产品，先根据所属的主产品找到主产品，然后将其添加进去
                MasterGoods master = masterMap.get(q);
                master.addSlaveGoods(new SlaveGoods(v, v * w));
            }
        }
        writer.write(String.valueOf(dynamicProgramming(money, n, masterMap)));
        writer.flush();
    }

    private static int dynamicProgramming(int money, int n, Map<Integer, MasterGoods> masterMap) {
        int[] dp = new int[money + 1];
        //遍历所有主产品，分组背包，将每一个主产品分为一组，其中的每一组主附产品的搭配情况为组内的具体情况，只能选择一种
        for (Map.Entry<Integer, MasterGoods> entry : masterMap.entrySet()) {
            MasterGoods master = entry.getValue();
            List<SlaveGoods> slaveList = master.slaveList;
            //题目规定了，物品都是10元的倍数，所以j可以每次自减10
            for (int j = money; j >= 0; j -= 10) {
                //遍历每一种选择的情况，二进制状态压缩
                for (int status = 0; status < 1 << slaveList.size(); status++) {
                    int v = master.v, w = master.w;
                    //找到具体的选择情况
                    for (int i = 0; i < slaveList.size(); i++) {
                        if (((status >> i) & 1) == 1) {
                            v += slaveList.get(i).v;
                            w += slaveList.get(i).w;
                            if (v > j) break;
                        }
                    }
                    if (j >= v) dp[j] = Math.max(dp[j], dp[j - v] + w);
                }
            }
        }
        return dp[money];
    }

    private static class MasterGoods {
        private int v;
        private int w;
        private List<SlaveGoods> slaveList = new ArrayList<>();

        public MasterGoods(int v, int w) {
            this.v = v;
            this.w = w;
        }

        public void addSlaveGoods(SlaveGoods slaveGoods) { this.slaveList.add(slaveGoods); }
    }

    private static class SlaveGoods {
        private int v;
        private int w;

        public SlaveGoods(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
}
